#define _CRT_SECURE_NO_WARNINGS 1

//struct ListNode* middleNode(struct ListNode* head) {
//    int count = 0;
//    struct ListNode* p = head;
//    while (p != NULL)
//    {
//        count++;
//        p = p->next;
//    }
//    int i = 1;
//    while (head != NULL)
//    {
//        if (i == count / 2 + 1)
//        {
//            break;
//        }
//        i++;
//        head = head->next;
//    }
//    return head;
//}

//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* frist = head;
//    struct ListNode* slow = head;
//    int i = 1;
//    while (frist != NULL)
//    {
//        if (i % 2 == 0 && i != 2)
//        {
//            slow = slow->next;
//        }
//        frist = frist->next;
//        i++;
//    }
//    if (i != 2)
//    {
//        slow = slow->next;
//    }
//    return slow;
//}

//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//    // write code here
//    struct ListNode* frist = pListHead;
//    struct ListNode* slow = pListHead;
//    while (k--)
//    {
//        if (frist)
//        {
//            frist = frist->next;
//        }
//        else {
//            return NULL;
//        }
//    }
//    while (frist)
//    {
//        frist = frist->next;
//        slow = slow->next;
//    }
//    return slow;
//}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode head;
    head.next = NULL;
    struct ListNode* end = &head;
    struct ListNode* p1 = list1;
    struct ListNode* p2 = list2;
    while (p1 && p2)
    {
        if (p1->val > p2->val)
        {
            end->next = p2;
            end = p2;
            p2 = p2->next;
        }
        else
        {
            end->next = p1;
            end = p1;
            p1 = p1->next;
        }
    }
    if (p1)
    {
        end->next = p1;
    }
    else
    {
        end->next = p2;
    }
    return head.next;
}